SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Mark–compact algorithm</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Mark–compact algorithm</span></span>

</h1>

</header>

In <a href="Computer_science" title="Computer science">computer science</a>, a <b>mark–compact algorithm</b> is a type of <a href="Garbage_collection_(computer_science)" title="Garbage collection (computer science)">garbage collection</a> <a href="Algorithm" title="Algorithm">algorithm</a> used to reclaim <a href="Unreachable_memory" title="Unreachable memory">unreachable memory</a>. Mark–compact algorithms can be regarded as a combination of the <a href="Mark%E2%80%93sweep_algorithm" class="mw-redirect" title="Mark–sweep algorithm">mark–sweep algorithm</a> and <a href="Cheney's_algorithm" title="Cheney's algorithm">Cheney's copying algorithm</a>. First, reachable objects are marked, then a compacting step relocates the reachable (marked) objects towards the beginning of the heap area. Compacting garbage collection is used by modern <a href="Java_virtual_machine" title="Java virtual machine">JVMs</a>, <a href="Microsoft" title="Microsoft">Microsoft</a>'s <a href="Common_Language_Runtime" title="Common Language Runtime">Common Language Runtime</a> and by the <a href="Glasgow_Haskell_Compiler" title="Glasgow Haskell Compiler">Glasgow Haskell Compiler</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithms">Algorithms</h2></div>

<p>After marking the live objects in the heap in the same fashion as the <a href="Mark%E2%80%93sweep_algorithm" class="mw-redirect" title="Mark–sweep algorithm">mark–sweep algorithm</a>, the heap will often be <a href="Fragmentation_(computer)" class="mw-redirect" title="Fragmentation (computer)">fragmented</a>. The goal of mark–compact algorithms is to shift the live objects in memory together so the fragmentation is eliminated. The challenge is to correctly update all pointers to the moved objects, most of which will have new memory addresses after the compaction. The issue of handling pointer updates is handled in different ways.

</p>

<div class="mw-heading mw-heading3"><h3 id="Table-based_compaction">Table-based compaction</h3></div>

<p>A table-based algorithm was first described by Haddon and Waite in 1967.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> It preserves the relative placement of the live objects in the heap, and requires only a constant amount of overhead.

</p><p>Compaction proceeds from the bottom of the heap (low addresses) to the top (high addresses). As live (that is, marked) objects are encountered, they are moved to the first available low address, and a record is appended to a <b>break table</b> of relocation information. For each live object, a record in the break table consists of the object's original address before the compaction and the difference between the original address and the new address after compaction. The break table is stored in the heap that is being compacted, but in an area that is marked as unused. To ensure that compaction will always succeed, the minimum object size in the heap must be larger than or the same size as a break table record.

</p><p>As compaction progresses, relocated objects are copied towards the bottom of the heap. Eventually an object will need to be copied to the space occupied by the break table, which now must be relocated elsewhere. These movements of the break table, (called <i>rolling the table</i> by the authors) cause the relocation records to become disordered, requiring the break table to be <a href="Comparison_sort" title="Comparison sort">sorted</a> after the compaction is complete. The cost of sorting the break table is <i><a href="Big_O_notation" title="Big O notation">O</a></i>(<i>n</i> log <i>n</i>), where <i>n</i> is the number of live objects that were found in the mark stage of the algorithm.

</p><p>Finally, the break table relocation records are used to adjust pointer fields inside the relocated objects. The live objects are examined for pointers, which can be looked up in the sorted break table of size <i>n</i> in O(log <i>n</i>) time if the break table is sorted, for a total running time of <i>O</i>(<i>n</i> log <i>n</i>). Pointers are then adjusted by the amount specified in the relocation table.

</p>

<div class="mw-heading mw-heading3"><h3 id="LISP_2_algorithm">LISP 2 algorithm</h3></div>

<p>In order to avoid <i>O</i>(<i>n</i> log <i>n</i>) complexity, the <span class="nowrap"><a href="LISP_2" title="LISP 2">LISP 2</a></span> algorithm uses three different passes over the heap. In addition, heap objects must have a separate forwarding pointer slot that is not used outside of garbage collection.

</p><p>After standard marking, the algorithm proceeds in the following three passes:

</p>

<ol><li>Compute the forwarding location for live objects.

<ul><li>Keep track of a <i>free</i> and <i>live</i> pointer and initialize both to the start of heap.</li>

<li>If the <i>live</i> pointer points to a live object, update that object's forwarding pointer to the current <i>free</i> pointer and increment the <i>free</i> pointer according to the object's size.</li>

<li>Move the <i>live</i> pointer to the next object</li>

<li>End when the <i>live</i> pointer reaches the end of heap.</li></ul></li>

<li>Update all pointers

<ul><li>For each live object, update its pointers according to the forwarding pointers of the objects they point to.</li></ul></li>

<li>Move objects

<ul><li>For each live object, move its data to its forwarding location.</li></ul></li></ol>

<p>This algorithm is <i>O</i>(<i>n</i>) on the size of the heap; it has a better complexity than the table-based approach, but the table-based approach's <i>n</i> is the size of the used space only, not the entire heap space as in the LISP2 algorithm. However, the LISP2 algorithm is simpler to implement.

</p>

<div class="mw-heading mw-heading3"><h3 id="The_Compressor">The Compressor</h3></div>

<p>The Compressor compaction algorithm<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> has the lowest complexity among compaction algorithms known today. It extends IBM’s garbage collection for Java.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

The serial version of the Compressor maintains a relocation map that maps the old address of each object to its new address (i.e., its address before compaction is mapped to its address after compaction). In a first pass, the mapping is computed for all objects in the heap. In a second pass, each object is moved to its new location (compacted to the beginning of the heap), and all pointers within it are modified according to the relocation map.

</p><p>The computation of the relocation map in the first pass can be made very efficient by working with small tables that do not require a pass over the entire heap. This keeps the Compressor complexity low, involving one pass over small tables and one pass over the full heap. This represents the best-known complexity for compaction algorithms.

</p><p>The Compressor also has a parallel version in which multiple compacting threads can work together to compact all objects in parallel. The Compressor also has a concurrent version in which compacting threads can work concurrently with the program, carefully allowing the program to access objects as they are being moved towards the beginning of the heap. The parallel and concurrent versions of the Compressor make use of virtual memory primitives.

</p>

<ul><li><a href="Dead-code_elimination" title="Dead-code elimination">Dead-code elimination</a></li>

<li><a href="Tracing_garbage_collection" title="Tracing garbage collection">Tracing garbage collection</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFB._K._HaddonW._M._Waite1967" class="citation journal cs1">B. K. Haddon; W. M. Waite (August 1967). <a rel="nofollow" class="external text" href="https://academic.oup.com/comjnl/article-pdf/10/2/162/963555/10-2-162.pdf">"A compaction procedure for variable-length storage elements"</a> <span class="cs1-format">(PDF)</span>. <i>Computer Journal</i>. <b>10</b> (2): <span class="nowrap">162–</span>165. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1093%2Fcomjnl%2F10.2.162">10.1093/comjnl/10.2.162</a></span>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFKermanyPetrank2006" class="citation conference cs1">Kermany, Haim; <a href="Erez_Petrank" title="Erez Petrank">Petrank</a>, Erez (June 2006). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/1133255.1134023"><i>The Compressor: concurrent, incremental, and parallel compaction Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation</i></a></span>. Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation. pp. <span class="nowrap">354–</span>363. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1133255.1134023">10.1145/1133255.1134023</a>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFAbuaiadhOssiaPetrankSilbershtein2004" class="citation conference cs1">Abuaiadh, Diab; Ossia, Yoav; Petrank, Erez; Silbershtein, Uri (October 2004). <span class="id-lock-subscription" title="Paid subscription required"><a rel="nofollow" class="external text" href="https://dl.acm.org/doi/10.1145/1028976.1028995"><i>An Efficient Parallel Heap Compaction Algorithm</i></a></span>. ACM Conference on Object-Oriented Programming, Systems, Languages, and Applications. pp. <span class="nowrap">224–</span>236. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F1028976.1028995">10.1145/1028976.1028995</a>.</cite></span>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Memory_management1048" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Memory_management1048" style="font-size:114%;margin:0 4em"><a href="Memory_management" title="Memory management">Memory management</a></div></th></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><a href="Memory_management_(operating_systems)" title="Memory management (operating systems)">Memory management as a function of an operating system</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Hardware</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Memory_management_unit" title="Memory management unit">Memory management unit</a> (MMU)</li>

<li><a href="Translation_lookaside_buffer" title="Translation lookaside buffer">Translation lookaside buffer</a> (TLB)</li>

<li><a href="Input%E2%80%93output_memory_management_unit" title="Input–output memory management unit">Input–output memory management unit</a> (IOMMU)</li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Virtual_memory" title="Virtual memory">Virtual memory</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Demand_paging" title="Demand paging">Demand paging</a></li>

<li><a href="Memory_paging" title="Memory paging">Memory paging</a></li>

<li><a href="Page_table" title="Page table">Page table</a></li>

<li><a href="Virtual_memory_compression" title="Virtual memory compression">Virtual memory compression</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Memory_segmentation" title="Memory segmentation">Segmentation</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Protected_mode" title="Protected mode">Protected mode</a></li>

<li><a href="Virtual_8086_mode" title="Virtual 8086 mode">Virtual 8086 mode</a></li>

<li><a href="X86_memory_segmentation" title="X86 memory segmentation">x86 memory segmentation</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Memory_allocator" class="mw-redirect" title="Memory allocator">Allocator</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Dlmalloc" class="mw-redirect" title="Dlmalloc">dlmalloc</a></li>

<li><a href="Hoard_memory_allocator" title="Hoard memory allocator">Hoard</a></li>

<li><a href="Jemalloc" class="mw-redirect" title="Jemalloc">jemalloc</a></li>

<li><a href="Libumem" title="Libumem">libumem</a></li>

<li><a href="Mimalloc" title="Mimalloc">mimalloc</a></li>

<li><a href="Ptmalloc" class="mw-redirect" title="Ptmalloc">ptmalloc</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Manual_memory_management" title="Manual memory management">Manual</a> means</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Static_variable" title="Static variable">Static memory allocation</a></li>

<li><a href="C_dynamic_memory_allocation" title="C dynamic memory allocation">C dynamic memory allocation</a></li>

<li><a href="New_and_delete_(C%2B%2B)" title="New and delete (C++)">new and delete (C++)</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Garbage_collection_(computer_science)" title="Garbage collection (computer science)">Garbage<br>collection</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automatic_Reference_Counting" title="Automatic Reference Counting">Automatic Reference Counting</a></li>

<li><a href="Boehm_garbage_collector" title="Boehm garbage collector">Boehm garbage collector</a></li>

<li><a href="Cheney's_algorithm" title="Cheney's algorithm">Cheney's algorithm</a></li>

<li><a href="Concurrent_mark_sweep_collector" title="Concurrent mark sweep collector">Concurrent mark sweep collector</a></li>

<li><a href="Finalizer" title="Finalizer">Finalizer</a></li>

<li><a href="Garbage_(computer_science)" title="Garbage (computer science)">Garbage</a></li>

<li><a href="Garbage-first_collector" title="Garbage-first collector">Garbage-first collector</a></li>

<li><a href="Reference_counting" title="Reference counting">Reference counting</a></li>

<li><a href="Tracing_garbage_collection" title="Tracing garbage collection">Tracing garbage collection</a></li>

<li><a href="Weak_reference" title="Weak reference">Strong reference</a></li>

<li><a href="Weak_reference" title="Weak reference">Weak reference</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Memory_safety" title="Memory safety">Safety</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Buffer_overflow" title="Buffer overflow">Buffer overflow</a></li>

<li><a href="Buffer_over-read" title="Buffer over-read">Buffer over-read</a></li>

<li><a href="Dangling_pointer" title="Dangling pointer">Dangling pointer</a></li>

<li><a href="Stack_overflow" title="Stack overflow">Stack overflow</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Issues</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Fragmentation_(computing)" title="Fragmentation (computing)">Fragmentation</a></li>

<li><a href="Memory_leak" title="Memory leak">Memory leak</a></li>

<li><a href="Unreachable_memory" title="Unreachable memory">Unreachable memory</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Other</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automatic_variable" title="Automatic variable">Automatic variable</a></li>

<li><a href="International_Symposium_on_Memory_Management" title="International Symposium on Memory Management">International Symposium on Memory Management</a></li>

<li><a href="Region-based_memory_management" title="Region-based memory management">Region-based memory management</a></li>

<li><a href="Memory_pool" title="Memory pool">Memory pool</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Memory management</li>

<li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Virtual memory</li>

<li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Automatic memory management</li>

<li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Memory management algorithms</li>

<li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Memory management software</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-06-20" href="https://en.wikipedia.org/wiki/?title=Mark%E2%80%93compact_algorithm&oldid=1296440599">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>